public class CopyRandomList {

    /**
     * 用map保存老节点和新节点
     * 再将老节点的next和random通过map找到对应的新节点，
     * 将新节点的next和random指向找到的节点
     */

//    public Node copyRandomList(Node head) {
//        if (head == null) return null;
//        Node temp = head;
//        List<Node> origin = new ArrayList<>();
//        while (temp != null) {
//            origin.add(temp);
//            temp = temp.next;
//        }
//        List<Node>[] random = new ArrayList[origin.size()];
//        for (int i = 0; i < random.length; i++) {
//            random[i] = new ArrayList<>();
//        }
//        Node dummyHead = new Node(0);
//        Node newHead = dummyHead;
//        temp = head;
//        while (temp != null) {
//            newHead.next = new Node(temp.val);
//            newHead = newHead.next;
//            temp = temp.next;
//        }
//        temp = head;
//        Node temp2 = dummyHead.next;
//        while (temp != null) {
//            if (temp.random != null) {
//                random[origin.indexOf(temp.random)].add(temp2);
//            }
//            temp = temp.next;
//            temp2 = temp2.next;
//        }
//        temp = dummyHead.next;
//        int i = 0;
//        while (temp != null) {
//            if (random[i].size() != 0) {
//                for (int j = 0; j < random[i].size(); j++) {
//                    random[i].get(j).random = temp;
//                }
//            }
//            temp = temp.next;
//            i++;
//        }
//        return dummyHead.next;
//    }
//
//    HashMap<Node, Node> maps = new HashMap<>();
//    public Node copyRandomList(Node head) {
//        if (head == null) return null;
//        if (!maps.containsKey(head)) {
//            Node node = new Node(head.val);
//            maps.put(head, node);
//            node.next = copyRandomList(head.next);
//            node.random = copyRandomList(head.random);
//        }
//        return maps.get(head);
//    }
//
//}
//
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
}
